package com.javaspeak.algorithm.sort.quicksort;

import org.apache.log4j.Logger;

/**
 * Quick Sort is as the name suggests a quick way of sorting large arrays.
 *
 * Assuming data:
 *
 *     Unsorted: 10 2 5 7 3 8 4 1 6 9
 *
 * The output of this programme would be:
 *
 * .0 [main] DEBUG com.javaspeak.algorithm.sort.quicksort.QuickSorterTest  -
 * Unsorted: 10 2 5 7 3 8 4 1 6 9
 *
 * 3 [main] DEBUG com.javaspeak.algorithm.sort.quicksort.QuickSorter  -
 * New pivot:  <10>  2   5   7  [3]  8   4   1   6  <9>
 * Swapping 10 with 1 (indexes 0:7)
 * After swap: <1>  2   5  [7]  3   8   4   10   6  <9>
 * Swapping 5 with 3 (indexes 2:4)
 * After swap: <1>  2   3  [7]  5   8   4   10   6  <9>
 * ...New pivot:  <1> [2] <3>  7   5   8   4   10   6   9
 * ...New pivot:   1   2   3  <7>  5   8  [4]  10   6  <9>
 * ...Swapping 7 with 4 (indexes 3:6)
 * ...After swap:  1   2   3  <4> [5]  8   7   10   6  <9>
 * ......New pivot:   1   2   3   4  <5>  8  [7]  10   6  <9>
 * ......Swapping 8 with 6 (indexes 5:8)
 * ......After swap:  1   2   3   4  <5>  6   7  [10]  8  <9>
 * .........New pivot:   1   2   3   4  <5> <6>  7   10   8   9
 * .........New pivot:   1   2   3   4   5   6   7  <10> [8] <9>
 * .........Swapping 10 with 8 (indexes 7:8)
 * .........After swap:  1   2   3   4   5   6   7  <8> [10] <9>
 * ............New pivot:   1   2   3   4   5   6   7   8  <10> <9>
 * ............Swapping 10 with 9 (indexes 8:9)
 * ............After swap:  1   2   3   4   5   6   7   8  <9> <10>
 *
 * 3 [main] DEBUG com.javaspeak.algorithm.sort.quicksort.QuickSorterTest  -
 * Sorted: 1 2 3 4 5 6 7 8 9 10
 *
 * Note that the numbers in the square brackets are the pivots. Note also that
 * sometimes the pivot itself is swapped with another number.
 *
 * @author John Dickerson
 */
public class QuickSorter {

    public static Logger logger = Logger.getLogger( QuickSorter.class );

    /**
     * Used for debug purposes
     *
     * @param recursiveLevel  This number is used to get the number of spaces
     * for the indent before writing a line of text
     * @return an indent made up of spaces
     */
    private static String getIndent( int recursiveLevel ){

        String indent = "";

        for ( int i=0; i<recursiveLevel; i++ ){

            indent = indent + "...";
        }

        return indent;
    }


    /**
     * This method is used only for debugging purposes.
     *
     * @param numbers The array of numbers we wish to debug
     * @param startIndex  The start index of the numbers we wish to sort
     * @param endIndex The end index of the numbers we wish to sort
     * @param pivotIndex The pivot
     * @param recursiveLevel The number of indents at the beginning of the line.
     * Each indent is 3 spaces.
     * @return a line that looks something like:
     * <p>
     * 1 2 3 <7> 5 8 [4] 10 6 <9>
     * <p>
     * Note that <7> is the start of the sorting range, <9> is the end of the
     * sorting range and [4] is the pivot
     */
    private static String debug(
            int[] numbers, int startIndex,
                int endIndex, int pivotIndex, int recursiveLevel ){

        StringBuilder sb = new StringBuilder();

        for ( int i=0; i<numbers.length; i++ ){

            if ( i == startIndex ||  i == endIndex ){

                sb.append( "<" ).append( numbers[ i ] ).append( "> " );
            }
            else if ( i == pivotIndex ){

                sb.append( "[" ).append( numbers[ i ] ).append( "] " );
            }
            else {

                sb.append( " " ).append( numbers[ i ] ).append( "  " );
            }
        }

        return sb.toString();
    }

    /**
     *
     * Swaps the values at index startIndexMutable and endIndexMutable of
     * the array called numbers
     *
     * @param numbers array of numbers we are sorting
     * @param startIndexMutable index of value at left hand side of array
     * @param endIndexMutable index of value at right hand
     */
    private static void swap(
            int[] numbers, int startIndexMutable, int endIndexMutable,
                int recursiveLevel, StringBuilder sb ){

        if ( logger.isDebugEnabled() ){

            sb.append( "\n" );
            sb.append( getIndent( recursiveLevel ) );
            sb.append( "Swapping " );
            sb.append( numbers[ startIndexMutable ] );
            sb.append( " with " );
            sb.append( numbers[ endIndexMutable ] );
            sb.append( " (indexes " );
            sb.append( startIndexMutable ).append( ":" );
            sb.append( endIndexMutable );
            sb.append( ")" );
            sb.append( "\n" );
        }

        int temp = numbers[ startIndexMutable ];
        numbers[ startIndexMutable ] = numbers[ endIndexMutable ];
        numbers[ endIndexMutable ] = temp;
    }



    /**
     * Note that this method calls itself
     *
     * @param numbers  The array of numbers to sort
     * @param startIndex  The start index of the range of numbers we wish to
     * sort
     * @param endIndex  The end index of the range of numbers we wish to sort
     * @param recursiveLevel  used for debugging purposes to work out how much
     * to indent a line when printing output to the console
     * @param sb  used for debugging. sb is a StringBuilder which is printed to
     * the screen at the end of the sort
     */
    private static void sortRecursive(
            int[] numbers, int startIndex, int endIndex, int recursiveLevel,
                StringBuilder sb ){

        int pivotIndex = startIndex + ( endIndex - startIndex ) / 2;

        int pivot = numbers[ pivotIndex ];

        if ( logger.isDebugEnabled() ){

            sb.append( "\n" );

            sb.append( getIndent( recursiveLevel ) );
            sb.append( "New pivot:  " );
            sb.append( debug( numbers, startIndex, endIndex, pivotIndex,
                    recursiveLevel ) );
        }


        int startIndexMutable = startIndex;
        int endIndexMutable = endIndex;

        while ( startIndexMutable <= endIndexMutable ){

            while ( numbers[ startIndexMutable ] < pivot ){

                startIndexMutable++;
            }

            while ( numbers[ endIndexMutable ] > pivot ){

                endIndexMutable--;
            }

            if ( startIndexMutable <= endIndexMutable ) {

                if ( startIndexMutable != endIndexMutable ){

                    swap( numbers, startIndexMutable, endIndexMutable,
                            recursiveLevel, sb );

                    sb.append( getIndent( recursiveLevel ) );
                    sb.append( "After swap: " );

                    sb.append(
                          debug( numbers, startIndex,
                                     endIndex, pivot, recursiveLevel ) );
                }

                startIndexMutable++;
                endIndexMutable--;
            }
        }

        int newRecursiveLevel = recursiveLevel + 1;

        if ( startIndex < endIndexMutable ){

            // sort left hand side in range which we have not sorted yet
            sortRecursive( numbers, startIndex, endIndexMutable,
                    newRecursiveLevel, sb );
        }

        if ( startIndexMutable < endIndex ){

            // sort right hand side in range which we have not sorted yet
            sortRecursive( numbers, startIndexMutable, endIndex,
                    newRecursiveLevel, sb );
        }

    }


    /**
     * Main method
     *
     * @param numbers no arguments required
     */
    public static void sort( int[] numbers ){

        int recursiveLevel = 0;
        StringBuilder sb = new StringBuilder();

        sortRecursive( numbers, 0, numbers.length - 1, recursiveLevel, sb );

        // print debug info
        sb.append( "\n" );
        logger.debug( sb );
    }
}
